package leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class Code011_MaxSubarraySumCircular {

    // 暴力解法
    public static int maxSubarraySumCircular(int[] nums) {

        int n = nums.length;
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < 2 * n - 1; i++) {
            int sum = 0;
            for (int j = i; j < n + i; j++) {
                sum += nums[j % n];
                maxValue = Math.max(maxValue, sum);
            }
        }
        return maxValue;
    }

    // 前缀和 + 双端队列
    public static int maxSubarraySumCircular2(int[] nums) {
        int n = nums.length;
        int[] preSum = new int[2 * n + 1];
        preSum[0] = 0;
        for (int i = 0; i < 2 * n; i++) {
            preSum[i + 1] = preSum[i] + nums[i % n];
        }
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(0);
        int maxSum = nums[0];
        for (int i = 1; i < 2 * n; i++) {
            if(deque.peekFirst() < i - n){   // 滑动窗口大小为 n-1
                deque.pollFirst();
            }
            maxSum = Math.max(maxSum, preSum[i] - preSum[deque.peekFirst()]);

            while(!deque.isEmpty() && preSum[deque.peekLast()] > preSum[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2};
        int res = maxSubarraySumCircular2(nums);
        System.out.println(res);
    }
}
